/*给一个数组，寻找其中的一个连续子数组，要求和最大（不用记录数组，只需要计算最大和就可以了）
输入：[1,2,-5,3,5,1] 和最大的子数组应该是[3,5,1]，所以输出9
输入：[1,2,-5,3,-1,5,1]，和最大的子数组是[3,-1,5,1]，所以输出8
实现这个算法，并且说出你这个算法的时间复杂度，争取找到O(n)的算法，*/
#include<iostream>
#include<vector>
#include <string.h>
/*对于长度为n的数组，其子数组个数为1+2+3+...+n，即n*（n+1）/2个子数组。如果依次计算这些子数组的值并进行大小比较，则时间复杂度为O（n^2）。
思路，依次从左往右计算，计算各点左边所有数之和并存储，若某一点及其左边数组之和为负数，则表明
1.该点左侧的所有子数组的最大值已经被记录
2.且这一段对后面部分和的贡献为负值
舍去这一段，建立新的数组再次重复过程，即可找出最大的子数组之和。
*/
int getAdditionOfSubarray(std::vector<int> input)
{
	int length = input.size();
	int sum=0;
	int k = 1;
	int temp=0;//存储子数组之和
	do
	{
		for (int i = input.size()- length; i < k; ++i)        //依次求子数组之和，当有一段子数组贡献为负值时，将其舍弃，循环初始值改变。
		{
			sum += input[i];
		}		
		if (sum < 0)
		{
		input.erase(input.begin(), input.begin() + k); 
			length -= k;
			k = 1;			
		}
		else
		{
		k++;
		}
		if (sum >= temp)
		{
			temp = sum;
		}
		sum = 0;
	} 
	while (k<=length);
	return temp;
}


int main(int argc, char** argv)
{
	
	/*std::vector<int>input;
	int temp,result;
	for (int i = 0; i < 10; ++i) 
	{
		std::cin >> temp;
		input.push_back(temp);//依次输入数组值
	}*/
	std::vector<int>input{ 1,2,-5,3,-1,5,1 };
	int result;
	result = getAdditionOfSubarray(input);
	std::cout << "最大子数组之和为：" << result << std::endl;
}